package algorthm.systemTraning.quickSort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @className: QuickSort
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/9/26 17:04
 */
public class QuickSort {
    private static Logger logger = LoggerFactory.getLogger(QuickSort.class);
    private static int cnt = 0 ;

    public static void sortWithStack(int[] array){
        if(null == array || array.length < 2){
            return ;
        }
        Stack<Op> stack = new Stack();
        int L = 0 ;
        int R = array.length - 1 ;
        swap(array , (int)(Math.random()*R) , R);
        int[] rs = netherlandsFlag(array , L , R);
        stack.push(new Op(L , rs[0] - 1));
        stack.push(new Op( rs[1] + 1 , R));
        Op cur = null ;
        while(!stack.isEmpty()){
            cur = stack.pop();
            if(cur.getStart() >= cur.getEnd()){
                continue;
            }
            rs = netherlandsFlag(array , cur.getStart() , cur.getEnd());
            stack.push(new Op(cur.getStart() , rs[0] -1));
            stack.push(new Op(rs[1] + 1 , cur.getEnd()));
        }
    }
    public static void sortWithQueue(int[] array){
        if(null == array || array.length < 2){
            return ;
        }
        Queue<Op> queue = new LinkedList();
        int[] rs = netherlandsFlag(array , 0 , array.length - 1);
        queue.offer(new Op(0 , rs[0] - 1));
        queue.offer(new Op(rs[1] + 1 , array.length - 1));
        Op cur = null ;
        while(!queue.isEmpty()){
            cur = queue.poll();
            if(cur.getStart() >= cur.getEnd()){
                continue;
            }
            rs = netherlandsFlag(array , cur.getStart() , cur.getEnd());
            queue.offer(new Op(cur.getStart() , rs[0] -1));
            queue.offer(new Op(rs[1] + 1 , cur.getEnd()));
        }
    }
    public static class Op{
        private int start ;
        private int end ;
        public Op(int start , int end){
           this.start = start ;
           this.end = end ;
        }
        public int getStart(){
            return this.start ;
        }
        public int getEnd(){
            return this.end ;
        }
    }

    public static void sort(int[] array ){
        if(null == array || array.length <= 1){
            return;
        }
        process(array , 0 , array.length - 1);
    }
    public static void process(int[] array , int start , int end){
        if(start >= end){
            return;
        }
        swap(array , start + (int)(Math.random()*(end - start + 1)), end);
        int[] bound = netherlandsFlag(array , start , end);
        process(array , start , bound[0] -1);
        process(array , bound[1] + 1, end);
    }
    public static void swap(int[] array , int from , int to){
        if(from == to){
            return ;
        }
        array[from] = array[from] ^ array[to];
        array[to] = array[from] ^ array[to];
        array[from] = array[from] ^ array[to];
    }
    public static int detchLandFlag(int[] array , int start ,int end){
        if(array == null ){
            return -1 ;

        }
        if(start == end){
           return start ;
        }
        int L = start ,index = start ;
        while(index < end){
            // array[index] < array[end] , array[L] 和 array[index]
            if(array[index] < array[end]){
                swap(array , index , L++);
            }
            // array[index] >= array[end] 直接跳过
            index++;
        }
        swap(array , L , end);
        return L ;

    }


    public static int[] netherlandsFlag(int[] array , int start , int end){
        if(array == null){
            return new int[]{-1,-1};
        }
        if(start == end){
            return new int[]{start , end};
        }
        int L = start ;
        int R = end - 1;
        int index = start ;
        while(index < R +1){
            if(array[index] < array[end]){
                swap(array , index++ , L++);
            }else if(array[index] > array[end]){
                swap(array , index , R--);
            }else{
                index++;
            }
        }
        swap(array , end , R + 1);
        R++;
        // L = R+1 是大集合和小集合中间没有数的情况，array[end] 只有一个的情况。
        return new int[]{L , R};
    }
    public static void main(String[] args){
//        int[] array = {12 , 33 ,22 , 77 ,98};
//        int[] array = {12 , 100 , 1, -1 , 33 ,2 , 90 ,  77 ,98 ,99 , 102 , 98 , 98 , 32};
//        int[] array = {28, 30, 70, 2, 72, 83, 80};
        // 0, 4, 5, 8, 11, 15, 17, 17, 43, 28, 35, 50, 27, 38, 30, 49, 45, 51, 19, 53, 61, 54, 59, 64, 73, 73, 78, 79, 96, 99, 95, 87, 87]
//        int[] array = {83, 17, 65, 79, 9, 93, 41};
//        int[] array = {76, 5, 74, 82, 7, 51, 66, 52, 5};
//        int[] rs = netherlandsFlag(array , 0 , array.length - 1);
        int[] array = {14, 16, 27, 1, 84, 41, 31, 16, 15};
//        for(int i : rs){
//            System.out.print(i + ",");
//        }
//        System.out.println();
//        for(int i : array){
//           System.out.print(i + ",");
//        }
//        Arrays.sort(array);
//        sort(array);
//        sortWithStack(array);
        sortWithQueue(array);
        for(int i : array){
           System.out.print(i + ",");
        }
    }
}
